/*
 * Organizacion de computadoras (66.20) - TP1 1er Cuatrimestre 2013.

 * Archivo: ShellSort.S
 * 
 * Integrantes:
 * 
 *      Maximiliano Monzon (82341)
 *      Nahuel Lucero (90365)
 *      Juan Ignacio Lopez Pecora (84700)
 */

#include <mips/regdef.h>

.text
.align 2
.global shellsort
.ent shellsort

shellsort:
    .frame  $fp, 48, ra
    .set    noreorder
    .cpload t9
    .set    reorder

    # Se define el stack
    subu    sp, sp, 48
    sw      ra, 40(sp)
    sw      $fp, 36(sp)
    sw      gp, 32(sp)
    sw      a0, 48(sp)
    sw      a1, 52(sp)
    move    $fp, sp

    # Inicializo las variables.
    add     t0, zero, zero      # i = 0
    sw      t0, 16($fp)		    

    add     t1, zero, zero      # j = 0
    sw      t1, 20($fp)		     

    srl     t2, a1, 1           # increment = arraySize/2
    sw      t2, 24($fp)		     

    add     t3, zero, zero      # temp = 0
    sw      t3, 28($fp)		
	
loop_1:
    beqz    t2, fin_loop_1      # incremento <= 0 => fin_loop_01
    bltz    t2, fin_loop_1
    move    t0, zero		# i = 0

por_1:		
    subu    t5, a1, t0          # t5 <- arraysize - i
    blez    t5, fin_por_1	# i >= arraySize => fin_por_01

    move    t1, t0              # j = i
    sll     t5, t0, 2		# t5 <- i*4
    addu    t5, t5, a0		# t5 <- i*4 + words
    lw      t3, 0(t5)		# temp = words[i]

loop_2:
    sub     t5, t1, t2		# t5 <- j - increment
    bltz    t5, fin_loop_2	# (j -increment) < 0 => fin_loop_2

    # Volcado de t0 a t3 a memoria.
    sw      t0, 16($fp)
    sw      t1, 20($fp)
    sw      t2, 24($fp)
    sw      t3, 28($fp)

    # v0 <- strcasecmpmine (words[j-increment], temp)
    sub     t6, t1, t2		# t6 <- j-increment
    sll     t6, t6, 2		# t6 <- (j-increment) * 4
    addu    t6, t6, a0		# t6 <- words + (j - increment) * 4

    lw      a0, 0(t6)		# a0 <- words[j-increment]
    sw      a0, 0($fp)

    move    a1, t3		# a1 <- temp
    sw      a1, 4($fp)

    la      t9, strcasecmpmine
    jalr    t9                  # ejecución de la función

    # Levanta de memoria a0, a1 y t0 a t3.
    lw      t0, 16($fp)
    lw      t1, 20($fp)
    lw      t2, 24($fp)
    lw      t3, 28($fp)
    lw      a0, 48($fp)
    lw      a1, 52($fp)

    beqz    v0, fin_loop_2      
    bltz    v0, fin_loop_2          

    # words [j] = words [j-increment]

    sub     t6, t1, t2		# t6 <- j - increment
    sll     t6, t6, 2		# t6 <- (j-increment)*4
    addu    t6, t6, a0		# t6 <- words + (j-increment)*4
    lw      t5, 0(t6)		# t5 <- words [j-increment]
    sll     t7, t1, 2		# t7 <- j * 4
    addu    t7, a0, t7		# t7 <- words + j*4
    sw      t5, 0(t7)		# words[j]  words[j-increment]
    sub     t1, t1, t2		# j = j - incremento
    j       loop_2
			
fin_loop_2:			
    move    t6, t1		# t6 <- j
    sll     t6, t6, 2		# t6 <- j * 4
    addu    t6, a0, t6		# t6 <- words + j*4
    sw      t3, 0(t6)		# words[j] = temp
			
pre_fin_por_1:
    addi    t0, t0, 1	    	# i++
    j       por_1
			
fin_por_1:
    subu    t6, t2, 2           # t6 <- increment - 2
    beqz    t6, else            # increment == 2 => increment = 1
    mul     t2, t2, 5           # (increment <- increment * 5) / 11
    div     t2, t2, 11
    j       loop_1
else:
    addi    t2, zero, 1
    j       loop_1

fin_loop_1:
    # Se destruye el stack
    move    sp, $fp
    lw      $fp, 36(sp)
    lw      ra,  40(sp)
    lw      gp,  32(sp)
    addu    sp, sp, 48
    j       ra
          
.end    shellsort





